package org.jgs1904.apachepoidemo.Algorithm;

import org.apache.commons.math3.analysis.polynomials.PolynomialFunctionNewtonForm;

import java.util.Random;
import java.util.concurrent.ForkJoinPool;

/**
 * @author: 默苍璃
 * @date: 2024-01-11 15:59
 * <p>
 * 希尔排序
 * 缩小增量排序
 */
public class ShellSort {

    public static void main(String[] args) {


        Random random = new Random();
        int numberOfRecords = 100000;

        int[] array = new int[numberOfRecords];
        for (int i = 0; i < numberOfRecords; i++) {
            int randomNumber = random.nextInt(); // 生成一个随机整数
            array[i] = randomNumber;
        }

        long l = System.currentTimeMillis();
        // int[] array = {1, 55, 155, 133, 144, 233, 13, 4, 2, 4, 6, 55, 64, 212, 44, 33, 63};
        // 正序
        int gap = array.length / 2;
        int m = 1;

        while (gap != 0) {

            if (gap == 1) {
                // 正序
                for (int i = 0; i < array.length - 1; i++) {
                    int j = i;
                    while (true) {
                        if (array[j + 1] < array[j]) {
                            int temp = array[j];
                            array[j] = array[j + 1];
                            array[j + 1] = temp;
                            j--;
                        } else {
                            break;
                        }
                    }
                }
                break;
            }

            // for (int i = 0; i < gap; i++) {

            if (m > 1) {

                for (int j = 0; j < gap; j++) {
                    int g = gap * (array.length / gap);

                    while (g > 0) {
                        if (g - j - gap < array.length - 1 || g - j - gap < array.length - 1) {
                            break;
                        }
                        if (g - j - gap > 0 && array[g - j] < array[g - j - gap]) {
                            int temp = array[g - j];
                            array[g - j] = array[g - j - (gap)];
                            array[g - j - gap] = temp;
                        }
                        g = g - gap;
                    }
                }

            } else {
                for (int i = 0; i < gap; i++) {
                    if (array[i] > array[i + gap]) {
                        int temp = array[i];
                        array[i] = array[i + (gap)];
                        array[i + gap] = temp;
                    }
                }

            }

            gap = gap / 2;
            m++;
            System.out.println();
            System.out.println("____________________________________");
            for (int k : array) {
                System.out.print(k);
                System.out.print(",");

            }
        }

        for (int k : array) {
            System.out.println(k);
        }

        System.out.println("耗时");
        System.out.println(System.currentTimeMillis() - l);

        System.out.println("__________________________________");

    }


    // 核心代码---开始
    public static void sort(Comparable[] arr) {
        int j;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                Comparable tmp = arr[i];
                for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = tmp;
            }
        }
    }


    // int k = gap;
    // for (int j = 0; k > 0; k--) {
    //     for (int n = 0; n < m; n++) {
    //
    //         if ()
    //
    //     }
    //
    //     if (array[j] > (array[j + gap]) && gap * (j + 1) < array.length) {
    //         int temp = array[j];
    //         array[j] = array[j + gap];
    //         array[j + gap] = temp;
    //     }
    //
    //     // if (array[j] > (array[j + i])) {
    //     //
    //     // }
    //     j++;
    // }


    // int n = 1;
    // int j = m;
    //             for (int k = i; j > 0; j--) {
    //     System.out.println(array[k]);
    //     System.out.println(array[k + gap * n]);
    //     if (array[k] > array[k + (gap * n)]) {
    //         int temp = array[k];
    //         array[k] = array[k + (gap * n)];
    //         array[k + gap] = temp;
    //     }
    //     n++;
    // }

}
